package com.tgy.tree;

import lombok.Getter;

import java.util.*;

/**
 * @Author: tgy
 * @Date: 2020-09-08 10:05
 */
public class BinarySearchTree<E> extends BinaryTree<E>{


    private Comparator<E> comparator;

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public BinarySearchTree() {

    }

    /**
     * //添加元素
     * @param element
     */
    public E add(E element) {


        if (element == null) {

            throw new IllegalArgumentException("element 不能为null");
        }

        Node<E> tmpNode = root;
        Node<E> parentNode = null;
        int compareResult = 0;

        while (tmpNode != null) {

            compareResult = compare(element,tmpNode.element);

            parentNode = tmpNode;

            if (compareResult < 0 ) {

                tmpNode = tmpNode.left;

            }else if (compareResult > 0) {

                tmpNode = tmpNode.right;
            }else {

                // 相等则不添加
                E tmpElement = tmpNode.element;
                tmpNode.element = element;
                return tmpElement;
            }
        }

//        Node<E> newNode = new Node<>(element, parentNode);
        Node<E> newNode = createNode(element,parentNode);
        if (parentNode == null) {

            root = newNode;
        }else {

            if (compareResult < 0) {

                parentNode.left = newNode;

            }else if (compareResult > 0) {

                parentNode.right = newNode;
            }
        }
        size++;
        addAdjustTree(newNode);
        return null;
    }

    /**
     * 删除元素
     * @param element
     */
    public Node<E> remove(E element) {

        Node<E> node = inorderTaversalTree(element);

        if (node == null) {

            return null;
        }

        if (node.degree() == 2) {

            Node<E> nextNode = nextNode(node);

            E tmpElement = node.element;
            node.element = nextNode.element;
            node = nextNode;
            node.element = tmpElement;
        }

        if (node.degree() == 0) {

            if (node.parent != null) {

                if (node.equals(node.parent.left)) {

                    node.parent.left = null;
                }else {

                    node.parent.right = null;
                }

                removeAdjustTree(node);
            }else {

                root = null;
            }

        }else {

            Node<E> replaceNode = null;
            if (node.parent != null) {

                if (node.equals(node.parent.left)) {

                    node.parent.left = node.left != null?node.left:node.right;
                    node.parent.left.parent = node.parent;

                    replaceNode = node.parent.left;
                }else {

                    node.parent.right = node.left != null?node.left:node.right;
                    node.parent.right.parent = node.parent;

                    replaceNode = node.parent.right;
                }


            }else {

                root = node.left != null?node.left:node.right;
                root.parent = null;
                replaceNode = root;
            }
            removeAdjustTree(replaceNode);
        }
        size--;
//        node 的parent指向没有删除，可以使用parent往上查找。
//        removeAdjustTree(node);
        return node;
    }


    protected Node<E> createNode(E element,Node<E> parentNode) {

        return new Node<>(element,parentNode);
    }

    protected void addAdjustTree(Node<E> node){

    }

    protected void removeAdjustTree(Node<E> node){

    }

    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();

        sb.append("size=").append(size).append(" {");
//        printer(root,sb);
        levelPrinter(root,sb);
//        inorderTraversalTree(root, sb);
//        preorderTraversalTree(root,sb);
//        postorderTraversalTree(root,sb);
        sb.deleteCharAt(sb.length()-1).append("}");

        return sb.toString();
    }


    /**
     * 比较两个节点元素的大小
     * @param left
     * @param right
     * @return
     */
    private int compare(E left, E right) {

        if (this.comparator != null) {

            return comparator.compare(left,right);
        }

        return  ((Comparable<E>)left).compareTo(right);
    }

}
